#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<queue>
#include<vector>
#include<string>
#include<stack>
using namespace std;

class SeatManager {
public:
    priority_queue<int, vector<int>, greater<int>> qu;
    SeatManager(int n) {
        for (int i = 1; i <= n; ++i) qu.push(i);
    }

    int reserve() {
        int tmp = qu.top();
        qu.pop();
        return tmp;
    }

    void unreserve(int seatNumber) {
        qu.push(seatNumber);
    }
};

class Solution
{
public:
    int deleteAndEarn(vector<int>& nums) {
        int arr[10001] = { 0 };
        for (auto x : nums) arr[x] += x;
        vector<int> dp(10001);
        dp[0] = arr[0], dp[1] = max(arr[0], arr[1]);
        for (int i = 2; i < 10001; ++i)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[10000];
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        vector<int> dpf(n);
        auto dpg = dpf;
        dpf[2] = nums[2], dpg[1] = nums[1];
        for (int i = 2; i < n; ++i)
        {
            if (i >= 3 && i <= n - 2) dpf[i] = max(dpf[i - 1], dpf[i - 2] + nums[i]);
            dpg[i] = max(dpg[i - 1], dpg[i - 2] + nums[i]);
        }
        return max(dpf[n - 2] + nums[0], dpg[n - 1]);
    }

    int massage(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        vector<int> f(n);
        vector<int> g(n);
        f[0] = nums[0];
        for (int i = 1; i < n; ++i)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n - 1], f[n - 2]);
    }

    string solve(string s, string t) {
        int scur = s.size() - 1, tcur = t.size() - 1, carry = 0;
        string ret;
        while (scur >= 0 || tcur >= 0 || carry)
        {
            int sum = carry;
            if (scur >= 0) sum += s[scur--] - '0';
            if (tcur >= 0) sum += t[tcur--] - '0';
            ret = to_string(sum % 10) + ret;
            carry = sum / 10;
        }
        return ret;
    }

        struct ListNode {
        int val;
        ListNode* next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode* next) : val(x), next(next) {}
        
    };

    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* newl1 = reverseList(l1), * newl2 = reverseList(l2);
        int carry = 0;
        ListNode* newhead = new ListNode(-1);
        ListNode* cur = newhead;
        while (newl1 || newl2 || carry)
        {
            int sum = carry;
            if (newl1)
            {
                sum += newl1->val;
                newl1 = newl1->next;
            }
            if (newl2)
            {
                sum += newl2->val;
                newl2 = newl2->next;
            }
            ListNode* next = cur->next;
            cur->next = new ListNode(sum % 10);
            cur->next->next = next;

            carry = sum / 10;
        }
        return newhead->next;
    }

    string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int m = num1.size(), n = num2.size();
        vector<int> mul(m + n);
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                mul[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        int carry = 0;
        string ret;
        for (int num : mul)
        {
            carry += num;
            ret += carry % 10 + '0';
            carry /= 10;
        }
        while (carry)
        {
            ret += carry % 10 + '0';
            carry /= 10;
        }
        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
        
    };

    bool IsInTree(TreeNode* root, TreeNode* k)
    {
        if (root == nullptr) return false;
        return root == k
            || IsInTree(root->left, k)
            || IsInTree(root->right, k);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        if (root == p || root == q) return root;

        bool pleft = IsInTree(root->left, p);
        bool pright = !pleft;

        bool qleft = IsInTree(root->left, q);
        bool qright = !qleft;

        if ((qleft && pright) || (qright && pleft)) return root;
        else if (qleft && pleft) return lowestCommonAncestor(root->left, p, q);
        else return lowestCommonAncestor(root->right, p, q);
    }

    bool path(TreeNode* root, TreeNode* k, stack<TreeNode*>& st)
    {
        if (root == nullptr) return false;
        st.push(root);
        if (root == k) return true;
        if (path(root->left, k, st)) return true;
        if (path(root->right, k, st)) return true;
        st.pop();
        return false;
    }
    TreeNode* _lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> ps;
        stack<TreeNode*> qs;
        path(root, p, ps);
        path(root, q, qs);
        while (ps.top() != qs.top())
        {
            if (ps.size() > qs.size()) ps.pop();
            else if (ps.size() < qs.size()) qs.pop();
            else
            {
                ps.pop();
                qs.pop();
            }
        }
        return ps.top();
    }
};

int main()
{
    Solution s;
    s.solve("1","99");
    return 0;
}